package com.zwx.binary;

/**
 * 二分查找
 *
 * @author 文希
 * @create 2019-05-31 0:03
 */
public class BinarySelect {

    /**
     * 最基本的二分查找思路
     */
    private static int binarySelect(int[] array, int key) {
        int left = 0;
        int right = array.length - 1;

        //这里必须是<=
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] == key) {
                return mid;
            } else if (array[mid] < key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 查找第一个与key相等的元素
     */
    private static int findFirstEqual(int[] array, int key) {
        int left = 0;
        int right = array.length - 1;

        //这里必须是<=
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] >= key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (left < array.length && array[left] == key) {
            return left;
        }
        return -1;
    }

    /**
     * 查找最后一个与key相等的元素
     */
    private static int findLastEqual(int[] array, int key) {
        int left = 0;
        int right = array.length - 1;

        //这里必须是<=
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] <= key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (right >= 0 && array[right] == key) {
            return right;
        }
        return -1;
    }

    /**
     * 查找最后一个等于或者小于key的元素
     */
    private static int findLastSmallerEqual(int[] array, int key) {
        int left = 0;
        int right = array.length - 1;

        //这里必须是<=
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }

    /**
     * 查找最后一个小于key的元素
     */
    private static int findLastSmaller(int[] array, int key) {
        int left = 0;
        int right = array.length - 1;

        //这里必须是<=
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] >= key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }

    /**
     * 查找第一个等于或者大于key的元素
     */
    private static int findFirstEqualLarger(int[] array, int key) {
        int left = 0;
        int right = array.length - 1;

        // 这里必须是 <=
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] >= key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    /**
     * 查找第一个大于key的元素
     */
    private static int findFirstLarger(int[] array, int key) {
        int left = 0;
        int right = array.length - 1;

        // 这里必须是 <=
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3, 4, 5, 6};
       /* int i = binarySelect(arr, 4);
        System.out.println("i = " + i);*/
        int firstEqual = findLastEqual(arr, 3);
        System.out.println("firstEqual = " + firstEqual);
    }
    /**
     * 二分查找变种总结
     */
    // 这里必须是 <=
   /* while(left <=right){
        int mid = (left + right) / 2;
        if (array[mid] ? key) {
            //... right = mid - 1;
        } else {
            // ... left = mid + 1;
        }
    }
    return xxx;*/
    /**
     * 解决办法总结：
     * 1.首先判断出是返回left，还是返回right
     * 2.判断出比较符号int mid = (left + right) / 2;
     * if (array[mid] ? key) {
     *     //... right = xxx;
     * }
     * else {
     *     // ... left = xxx;
     * }
     *
     * // 查找小于等于key的元素
     * int mid = (left + right) / 2;
     * if (array[mid] >= key) {
     *     right = mid - 1;
     * }
     * else {
     *     left = mid + 1;
     * }
     *
     */
}
